#include "List.h"
#include "StopWatch.h"
#include "d_sort.h"
#include <iostream>
#include <vector>
#include <math.h>
#include <string>

//Array position definitions:
//Order is arr[SELECTION/QUICK] for algoName and oRel
//Order is arr[SELECTION/QUICK][VECTOR/LIST] for timeRel
//Order for all others is arr[SMALL/LARGE][SELECTION/QUICK][VECTOR/LIST]
#define SMALL 0
#define LARGE 1
#define SELECTION 0
#define QUICK 1
#define VECTOR 0
#define LIST 1

using namespace std;

void testQuickSort()
{
    List<int> l;
    randomNumber rand;
    for(int i=0; i<10000; i++)
        l.push(rand.random());
    l.quickSort();
    for(int i=0; i<l.getSize()-1; i++)
    {
        if(l.at(i) > l.at(i+1))
        {
            cout << "testQuickSort failed!" << endl;
            return;
        }
    }
    cout << "testQuickSort succeeded!" << endl;
}

void testSelectionSort()
{
    List<int> l;
    randomNumber rand;
    for(int i=0; i<10000; i++)
        l.push(rand.random());
    l.selectionSort();
    for(int i=0; i<l.getSize()-1; i++)
    {
        if(l.at(i) > l.at(i+1))
        {
            cout << "testSelectionSort failed!"<< endl;
            return;
        }
    }
    cout << "testSelectionSort succeeded!"<< endl;
}

void testReverse()
{
    List<int> l;
    randomNumber rand;
    for(int i=0; i<10000; i++)
        l.push(rand.random());
    l.selectionSort();
    l.reverse();
    for(int i=0; i<l.getSize()-1; i++)
    {
        if(l.at(i) < l.at(i+1))
        {
            cout << "testReverse failed!"<< endl;
            return;
        }
    }
    cout << "testReverse succeeded!"<< endl;
}

void main()
{
	StopWatch watch;
	randomNumber rand;
	int size[2] = {5000, 10000};
	string algoName[2] = {"Selection Sort", "Quick Sort"};
	double time[2][2][2];
	double timeRel[2][2];
	double oRel[2] = {pow((double)(size[LARGE]/size[SMALL]), 2),
		((double)size[LARGE]/(double)size[SMALL]) * log(((double)size[LARGE]/(double)size[SMALL]))};
    
	vector<int> v[2];
	List<int> l[2];

    cout << "Test sorting methods" << endl;
    testSelectionSort();
    testQuickSort();
    testReverse();

    cout << endl << "Create basis" << endl;
    for(int i=0; i<size[SMALL]; i++)
    {
        int value = (int)rand.random();
        v[SMALL].push_back(value);
        l[SMALL].push(value);
    }
	for(int i=0; i<size[LARGE]; i++)
	{
		int value = (int)rand.random();
		v[LARGE].push_back(value);
		l[LARGE].push(value);
	}

    cout << endl << "Start sorting arrays" << endl;
	for(int length=0; length<2; length++)
	{
		for(int algo=0; algo<2; algo++)
		{
			vector<int> testVector = v[length];		//Get the appropriate vector
			watch.start();							//Start the watch
			if(algo == SELECTION)	selectionSort(testVector);	//Perform sorting
			else	quicksort(testVector);
			time[length][algo][VECTOR] = watch.stop();//Stop and read time
			cout << "[VECTOR] "<< algoName[algo] << " with " << size[length] << " random numbers. Time: " << time[length][algo][VECTOR] << " seconds." << endl;

			List<int> testList = l[length];			//Get the appropriate vector
			watch.start();							//Start the watch
			if(algo == SELECTION)	testList.selectionSort();	//Perform sorting
			else	testList.quickSort();
			time[length][algo][LIST] = watch.stop();	//Stop and read time
			cout << "[MyLIST] "<< algoName[algo] << " with " << size[length] << " random numbers. Time: " << time[length][algo][LIST] << " seconds." << endl;
		}
	}

	cout<< endl << "Time relations: " << endl;
	for(int algo=0; algo<2; algo++)
	{
		for(int type=0; type<2; type++)
		{
			timeRel[algo][type] = time[LARGE][algo][type] / time[SMALL][algo][type];
		}
		cout<< "[VECTOR] Time relation for " << algoName[algo] << ": " << timeRel[algo][VECTOR] << endl;
		cout<< "[MyLIST] Time relation for " << algoName[algo] << ": " << timeRel[algo][LIST] << endl;
	}

	cout<< endl << "O-relations: " << endl;
	cout<< "O-relation for Selection Sort: " << oRel[SELECTION] << endl;
	cout<< "O-relation for Quick Sort: " << oRel[QUICK] << endl;

    system("PAUSE");
}